// 提交链接：https://leetcode.cn/problems/take-k-of-each-character-from-left-and-right/
// lc2516. 每种字符至少取 K 个
// 完成日期：2024/9/27
// c++ 哈希表 滑动窗口 字符串

class Solution {
public:
    int takeCharacters(string s, int k) {
        int n = s.length();
        unordered_map<char,int> m;
        for(char k : s)
            m[k - 'a']++;

        for(int i = 0; i < 3; ++i)
        {
            if(m[i] < k)
                return -1;
        }

        int ans = 0, i = 0;
        for(int j = 0; j < n; ++j)
        {
            int c = s[j] - 'a';
            m[c]--;   // 移入窗口，相当于不取走 c
            while(m[c] < k)   // 窗口之外的 c 不足 k
            {
                m[s[i] - 'a']++;   // 移出窗口，相当于取走 s[i]
                i++;
            }
                
            ans = max(ans , j - i + 1);
        }
        return n - ans;
    }
};